1. Field of the Invention
This invention relates to a method and apparatus for generating prime numbers used in cryptographic systems, and to a cryptographic system wherein the prime numbers generated are used.
2. Description of the Related Art
In today's world, characterized by sophisticated information utilization, important business documents and image information are transmitted and communicated in the form of electronic information over an infrastructure of computer networks. By its very nature, electronic information can be easily copied, making it extremely difficult to distinguish between the copy and the original, and information security has become a very serious problem. The realization of computer networks which support “shared computer resources,” “multi-access,” and “broad-area implementation” is particularly indispensable to the establishment of a high-level information society. However, that very realization involves aspects which are inconsistent with the security of information exchanged between authorized parties. An effective technique for eliminating that inconsistency is encryption technology, which up until now, in the course of human history, has been primarily used in the fields of military operations and foreign diplomacy.
Cryptography is the process of converting information so that its meaning cannot be understood by anyone other than the authorized parties. In cryptographic operations, the conversion of the original text (plaintext) that anyone can understand to text (ciphertext), the meaning of which cannot be understood by a third party, is called encryption, and the restoration of that cipher text to plaintext is called decryption. The overall system wherein this encryption and decryption are performed is called a cryptosystem. In the processes of encryption and decryption, respectively, secret information called encryption keys and decryption keys is employed. A secret decryption key is necessary at the time of decryption, and a party knowledgeable of that decryption key can decrypt the cipher text. In this manner, the confidentiality of the information is maintained by the encryption.
The encryption key and decryption key may be the same or they may be different. A cryptosystem wherein both keys are the same is called a common key cryptosystem, and the DES (Data Encryption Standards) adopted by the Bureau of Standards of the U.S. Department of Commerce is a typical example thereof. Cryptosystems called public key cryptosystems have been proposed which are examples of cryptosystems wherein the two keys used are different. With such a public key cryptosystem, the users employing the cryptosystem each produce a pair of keys, that is, an encryption key and a decryption key. The encryption key is disclosed in a public key list, and only the decryption key is kept secret. A characteristic of a public key cryptosystem is that, since the encryption key and the decryption key in the pair are different, the decryption key can be derived from the encryption key using a one-way function.
The public key cryptosystem is a revolutionary cryptosystem wherewith the encryption key is disclosed, and the three factors necessary to the establishment of a high-level information society noted earlier are satisfied. Much research has been done in the interest of utilizing such cryptosystems in such fields as information communications technology, and the RSA cryptosystem has been proposed as a typical public key cryptosystem. This RSA cryptosystem is predicated on the difficulty of factoring prime numbers with one-way functions (prime factor problem). Various techniques (E1 Gamal cryptosystem, etc.) have also been proposed for public key cryptosystems predicated on the difficulty of solving discrete logarithms.
Many modern cryptosystems have been employed which use the prime factor problem or discrete logarithm problem noted above. Therefore, how to handle prime numbers is extremely important in constructing a cryptosystem. Specifically, there is a pressing need to develop techniques for quickly and efficiently generating integers that are true prime numbers.
In general, when generating prime numbers, a prime candidate is first generated, a judgment is then rendered as to whether or not the generated prime candidate is a prime number (prime number judgment), and a candidate thus judged to be a prime number is generated as a prime number.
A standard method of generating prime candidates for prime number judgment is the trial division method. In the trial division method, odd numbers are randomly generated. Then an examination is performed to determine whether or not the generated odd numbers are evenly divisible by the prime numbers equal to or less than a given prime number B, in order from the smaller prime number (i.e. in the order of 3, 5, 7, . . . , B). Those odd numbers which are not evenly divisible by any of the prime numbers equal to or less than a given prime number B are deemed to be prime candidates.
The methods for prime number judgment include probabilistic primality testing methods such as the Rabin method and deterministic primality testing methods such as the Pocklington method. Comparing the probabilistic primality testing methods with the deterministic primality testing methods, the former do not provide a judgment error rate of zero, but the processing time is short, while the latter involve a long processing time but do provide a judgment error rate of zero.
Now, when prime numbers are used in cryptosystems that employ the prime factoring problem, such as the RSA cryptosystem, for example, it is of course desirable that the prime numbers used be such as will be highly resistant to attack by prime factoring methods. Among the typical prime factoring methods which are known are the P−1 method and the P+1 method. The P−1 method is an attack method wherewith it is relatively easy to prime factor a number N, using a prime number solution algorithm, in cases where N=PQ (where P and Q are primes), and P−1 is formed only from the product of small primes. Similarly, the P+1 method is an attack method wherewith it is relatively easy to prime factor a number N, using a prime number solution algorithm, in cases where N=PQ (where P and Q are primes), and P+1 is formed only from the product of small primes.
Thus it is crucial to be able to efficiently generate prime numbers that are highly resistant to attack by the P−1 and P+1 methods (known collectively as the P±1 method), particularly in cases where the prime numbers generated are used in a cryptosystem. With the conventional prime number generation methods described earlier, however, prime candidates are generated randomly without thought to the question of attack resistance. Hence there is a problem that such generation methods cannot efficiently generate prime numbers that are highly resistant to the P±1 method.